home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / db / esm-3.1 / esm-3 / usr / local / sm / src / serverlib / bitmap / generic.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-05-05  |  10.1 KB  |  465 lines
  1. /*
  2.  *   $RCSfile: generic.c,v $  
  3.  *   $Revision: 1.1.1.1 $  
  4.  *   $Date: 1996/05/04 21:55:34 $      
  5.  */ 
  6. /**********************************************************************
  7. * EXODUS Database Toolkit Software
  8. * Copyright (c) 1991 Computer Sciences Department, University of
  9. *                    Wisconsin -- Madison
  10. * All Rights Reserved.
  11. *
  12. * Permission to use, copy, modify and distribute this software and its
  13. * documentation is hereby granted, provided that both the copyright
  14. * notice and this permission notice appear in all copies of the
  15. * software, derivative works or modified versions, and any portions
  16. * thereof, and that both notices appear in supporting documentation.
  17. *
  18. * THE COMPUTER SCIENCES DEPARTMENT OF THE UNIVERSITY OF WISCONSIN --
  19. * MADISON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" CONDITION.  
  20. * THE DEPARTMENT DISCLAIMS ANY LIABILITY OF ANY KIND FOR ANY DAMAGES
  21. * WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  22. *
  23. * The EXODUS Project Group requests users of this software to return 
  24. * any improvements or extensions that they make to:
  25. *
  26. *   EXODUS Project Group 
  27. *     c/o David J. DeWitt and Michael J. Carey
  28. *   Computer Sciences Department
  29. *   University of Wisconsin -- Madison
  30. *   Madison, WI 53706
  31. *
  32. *     or exodus@cs.wisc.edu
  33. *
  34. * In addition, the EXODUS Project Group requests that users grant the 
  35. * Computer Sciences Department rights to redistribute these changes.
  36. **********************************************************************/
  37.  
  38. #include <stdio.h>
  39. #include "ess.h"
  40. #include "bit_funcs.h"
  41.  
  42.  
  43. /* Module bit.c : routines for bit maps manipulation
  44.     
  45.  
  46.    IMPORTS: NONE
  47.  
  48.    EXPORTS: Bit map manipulation routines
  49.  
  50.     clearmap(mapptr, mapsize) : clear all the bits in the map
  51.  
  52.     setmap(mapptr, mapsize) : set all the bits in the map
  53.  
  54.     countmap(mapptr, mapsize) : count and return the number of bit set 
  55.  
  56.     mapempty(mapptr, mapsize) : check if all the bits in the bit map 
  57.         are cleared, return TRUE if so, FALSE otherwise
  58.  
  59.     setbit(mapptr, pos) : set the (pos)th bit in the bit map
  60.  
  61.     clearbit(mapptr, pos) : clear the (pos)th bit in the bit map
  62.  
  63.     checkset(mapptr, pos) : check if the (pos)th bit in the bit map is set,
  64.         return TRUE if so, FLASE otherwise
  65.  
  66.     nextset(mapptr, mapsize, last) : given the position of the last bit 
  67.         found, find the next bit set and return its position 
  68.  
  69.     nextclear(mapptr, mapsize, last) : given the position of the last bit 
  70.         found, find the next bit cleared and return its position 
  71.  
  72.       shiftmap(mapptr, pos, len, amt)        shift bits (pos) to (pos+len-1)
  73.         of the bitmap amt bits.  If amt > 0, bits are shifted right.  
  74.         If amt < 0, bits are shifted left.
  75.  
  76.         Actually, this is a really lousy description of what
  77.         shiftmap does.  After testing the assembly language version,
  78.         what shiftmap actually does is replicate the pattern of bits
  79.         from positions (pos) to (pos+len-1) at the positions 
  80.             (pos+amt) to (pos+len+amt-1)
  81.  
  82.  
  83.    NOTES: Bits are numbered from 0 through (mapsize - 1).
  84. */
  85.  
  86.  
  87. /* these routines are derived from wiss's bit.c.  the shiftmap routine
  88. was added by dewitt 11/1/88 as, while shiftmap appeared in bit.s 
  89. it did not appear in bit.c */
  90.  
  91. #define    tBITMAP    0
  92.  
  93.  void
  94. printmap (
  95.     unsigned char    *mapptr,        /* start of bitmap */
  96.     int                mapsize         /* size of bitmap (bits) */
  97. )
  98. /* print a given bit map (on the standard output) in hexdecimal form
  99.  
  100.    Returns:
  101.     NONE
  102.  
  103.    Side Effects:
  104.     bit map printed on the standard output decive in hexdecimal 
  105.  
  106.    Errors:
  107.     NONE
  108. */
  109. {
  110.     register int i;
  111.     int    bytes;
  112.  
  113.     bytes = (mapsize-1)/BITSPERBYTE + 1;
  114.     printf("{");
  115.     for (i = 0; i < bytes; i++)
  116.         printf(i==0 ? "%03x" : " %03x", mapptr[i]);
  117.     printf("}");
  118. }
  119.  
  120.  
  121. /*
  122.     **************************************************************
  123.     *            map-wise operations                             *
  124.     **************************************************************
  125. */
  126.  
  127.  
  128.  void
  129. clearmap(
  130.     unsigned char    *mapptr,        /* start of bitmap */
  131.     int                mapsize         /* size of bitmap (bits) */
  132. )
  133. /* clear all the bits in the given bit map
  134.  
  135.    Returns:
  136.     NONE
  137.  
  138.    Side Effects:
  139.     All the bits in the bit map cleared
  140.  
  141.    Errors:
  142.     NONE
  143. */
  144. {
  145.     register int    count;
  146.  
  147.     for (count = (--mapsize / BITSPERBYTE) + 1; count--;  mapptr++)
  148.         *mapptr = 0;    /* clear word */
  149. }
  150.  
  151.  void
  152. setmap(
  153.     unsigned char    *mapptr,        /* start of bitmap */
  154.     int                mapsize         /* size of bitmap (bits) */
  155. )
  156. /* set all the bits in the given map
  157.  
  158.    Returns:
  159.     NONE
  160.  
  161.    Side Effects:
  162.     All the bits in the bit map cleared
  163.  
  164.    Errors:
  165.     NONE
  166. */
  167. {
  168.     register int    count;
  169.  
  170.     for (count = (--mapsize / BITSPERBYTE) + 1; count--;  mapptr++)
  171.         *mapptr = ~0;    /* set word */
  172. }
  173.  
  174.  int
  175. countmap(
  176.     unsigned char    *mapptr,        /* start of bitmap */
  177.     int                mapsize         /* size of bitmap (bits) */
  178. )
  179. /* count and return the number of bit set in the bit map
  180.  
  181.    Returns:
  182.     Number of bit set in the bit map
  183.  
  184.    Side Effects:
  185.     NONE
  186.  
  187.    Errors:
  188.     NONE
  189. */
  190. {
  191.     register int    count, mask;
  192.  
  193.     for (count = 0, mask = 1; mapsize; mapsize--)
  194.     {
  195.         if (*mapptr & mask)    /* bit set */
  196.             count++;
  197.  
  198.         if ((mask<<=1) == (1<<BITSPERBYTE)) /* advance to next bit */
  199.         {    /* cross word boundary */
  200.             mask = 1;    /* reset mask to 1     */
  201.             mapptr++;    /* advance map pointer */
  202.         }
  203.     }
  204.  
  205.     return(count);
  206. }
  207.  
  208. mapempty(
  209.     unsigned char    *mapptr,        /* start of bitmap */
  210.     int                mapsize         /* size of bitmap (bits) */
  211. )
  212. /* check if all the bits in the given bit map are cleared
  213.  
  214.    Returns:
  215.     TRUE if all the bits are cleared,
  216.     FALSE otherwise
  217.  
  218.    Side Effects:
  219.     NONE
  220.  
  221.    Errors:
  222.     NONE
  223. */
  224. {
  225.     register int     mask;
  226.  
  227.     for (mask = 1; mapsize; mapsize--)
  228.     {
  229.         if (*mapptr & mask)    /* bit set */
  230.             return(FALSE);
  231.  
  232.         if ((mask<<=1) == (1<<BITSPERBYTE)) /* advance to next bit */
  233.         {    /* cross word boundary */
  234.             mask = 1;    /* reset mask to 1     */
  235.             mapptr++;    /* advance map pointer */
  236.         }
  237.     }
  238.  
  239.     return(TRUE);
  240. }
  241.  
  242.  
  243. /*
  244.     **************************************************************
  245.     *            bit-wise operations                             *
  246.     **************************************************************
  247. */
  248.  
  249.  
  250.  void
  251. setbit(
  252.     unsigned char    *mapptr,
  253.     int    pos         /* bit position */
  254. )
  255. /* set the (pos)th bit in the bit map
  256.  
  257.    Returns:
  258.     NONE
  259.  
  260.    Side Effects:
  261.     the (pos)th bit in the bit map set
  262.  
  263.    Errors:
  264.     NONE
  265. */
  266. {
  267.     /* adjust word pointer and bit offset (pos) */
  268.     mapptr += pos / BITSPERBYTE;
  269.     pos %= BITSPERBYTE;
  270.  
  271.     *mapptr |= 1 << pos;         /* set bit */
  272. }
  273.  
  274.  void
  275. clearbit(
  276.     unsigned char    *mapptr,
  277.     int    pos         /* bit position */
  278. )
  279. /* clear the (pos)th bit in the bit map
  280.  
  281.    Returns:
  282.     NONE
  283.  
  284.    Side Effects:
  285.     the (pos)th bit in the map cleared
  286.  
  287.    Errors:
  288.     NONE
  289. */
  290. {
  291.     /* adjust word pointer and bit offset (pos) */
  292.     mapptr += pos / BITSPERBYTE;
  293.     pos %= BITSPERBYTE;
  294.  
  295.     *mapptr &= ~(1 << pos);        /* clear bit */
  296. }
  297.  
  298. checkset(
  299.     unsigned char    *mapptr,
  300.     int    pos         /* bit position */
  301. )
  302. /* check if the (pos)th bit in the bit map is set
  303.  
  304.    Returns:
  305.     TRUE if the (pos)th bit in the map is set
  306.     FLASE otherwise
  307.  
  308.    Side Effects:
  309.     NONE
  310.  
  311.    Errors:
  312.     NONE
  313. */
  314. {
  315.     /* adjust word pointer and bit offset (pos) */
  316.     mapptr += pos / BITSPERBYTE;
  317.     pos %= BITSPERBYTE;
  318.     
  319.     return((*mapptr & (1 << pos)) ? TRUE : FALSE);
  320. }
  321.  
  322. nextset(
  323.     unsigned char    *mapptr,
  324.     int                 mapsize,    /* start and size of the bit map */
  325.     int                last         /* last bit position */
  326. )
  327. /* given the position of the last bit found, find the next bit set in the map
  328.  
  329.    Returns:
  330.     the position of the next set bit in the map
  331.         -1 if no more, or if bad "last found" value passed in
  332.  
  333.    Side Effects:
  334.     NONE
  335.  
  336.    Errors:
  337.     NONE
  338. */
  339. {
  340.     register int    mask;
  341.  
  342.     if (last < -1) 
  343.         last = -1;
  344.     else if (last >= mapsize)
  345.         return(-1);
  346.  
  347.     /* set up starting bit position */
  348.     mapptr += (++last) / BITSPERBYTE;
  349.     mask = 1 << (last % BITSPERBYTE);
  350.  
  351.     for (mapsize -= last;        /* mapsize = # checkable bits left */
  352.          mapsize;            /* any bits left to check? */
  353.          last++, mapsize--)        /* inc position, dec counter */
  354.     {
  355.         if (*mapptr & mask)    /* next bit found */
  356.             return (last);
  357.  
  358.         if ((mask<<=1) == (1<<BITSPERBYTE)) /* advance to next bit */
  359.         {    /* cross word boundary */
  360.             mask = 1;    /* reset mask to 1     */
  361.             mapptr++;    /* advance map pointer */
  362.         }
  363.     }
  364.  
  365.     return(-1);
  366. }
  367.  
  368.  
  369. nextclear(
  370.     unsigned char    *mapptr,
  371.     int                 mapsize,    /* start and size of the bit map */
  372.     int                last         /* last bit position */
  373. )
  374. /* given position of the last bit found, find the next bit cleared in the map
  375.  
  376.    Returns:
  377.     the position of the next cleared bit in the map
  378.  
  379.    Side Effects:
  380.     NONE
  381.  
  382.    Errors:
  383.     NONE
  384. */
  385. {
  386.     register int    mask;
  387.  
  388.     if (last < -1 || last >= mapsize)
  389.         return(-1);
  390.  
  391.     /* set up starting bit position */
  392.     mapptr += (++last) / BITSPERBYTE;
  393.     mask = 1 << (last % BITSPERBYTE);
  394.  
  395.     for (mapsize -= last;        /* mapsize = # checkable bits left */
  396.          mapsize;            /* any bits left to check? */
  397.          last++, mapsize--)        /* inc position, dec counter */
  398.     {
  399.         if ((*mapptr & mask) == 0)    /* next bit found */
  400.             return (last);
  401.  
  402.         if ((mask<<=1) == (1<<BITSPERBYTE)) /* advance to next bit */
  403.         {    /* cross word boundary */
  404.             mask = 1;    /* reset mask to 1     */
  405.             mapptr++;    /* advance map pointer */
  406.         }
  407.     }
  408.  
  409.     return(-1);
  410. }
  411.  
  412.  
  413. /* 
  414.  
  415. shift bits (pos) to (pos+len-1) of the bitmap amt bits.  
  416. If amt > 0, bits are shifted right.  If amt < 0, bits are shifted left.
  417.  
  418. Actually, this is a really lousy description of what shiftmap does.  
  419. After testing the assembly language version, what shiftmap actually 
  420. does is replicate the pattern of bits from positions (pos) to (pos+len-1) 
  421. at the positions (pos+amt) to (pos+len+amt-1)
  422.  
  423. */
  424.  
  425.  void
  426. shiftmap(
  427.     unsigned char    *mapptr,
  428.     int                pos,    /* starting bit position */
  429.     int                len,    /* length of region to be shifted */
  430.     int                amt     /* number of bits the region is to be shifted */
  431.         /* if amt < 0, bits are shifted left.  if amt > 0
  432.         bits are shifted right */
  433. )
  434. {
  435.     register int curbit;
  436.     register int i;
  437.  
  438.     if (amt > 0)
  439.     {
  440.     /* shift right */
  441.     curbit = pos + len - 1; /* point at the last bit in the region as we 
  442.                 are going to start at the right and work left */
  443.     for (i=0;i<len;i++, curbit--)
  444.     {
  445.         if (checkset(mapptr, curbit))
  446.         {
  447.         setbit(mapptr, curbit+amt);
  448.         }
  449.         else clearbit(mapptr, curbit+amt);
  450.     }
  451.     }
  452.     else  /* amt < 0 - shift left */
  453.     {
  454.     curbit = pos;  /* start at first bit in region and move right */
  455.     for (i=0;i<len;i++, curbit++)
  456.     {
  457.         if (checkset(mapptr, curbit))
  458.         {
  459.         setbit(mapptr, curbit+amt);
  460.         }
  461.         else clearbit(mapptr, curbit+amt);
  462.     }
  463.     }
  464. }
  465.